#include "ArbolBMas.h"

using namespace Arboles;
using namespace Entidades;

ArbolBMas::ArbolBMas(string nombre) {

	Configuracion* config = Configuracion::getInstancia();
	string path = config->getPathArbol() + "arbol" + nombre + ".bin";
	int tamanioEstructuras = config->getTamanioBloque();

	this->archivoNodos = new ArchivoDeEstructurasFijas(path, tamanioEstructuras);

	string pathNodosLibres = config->getPathArbol() + "nodosLibres" + nombre + ".bin";
	this->nodosLibres = new ManejadorEstructurasLibres(pathNodosLibres);

	this->capacidadMinimaNodosInternos = config->getCapacidadMinimaNodoInterno();
	this->capacidadMaximaNodosInternos = config->getCapacidadMaximaNodoInterno();
	this->capacidadMinimaNodosHoja = config->getCapacidadMinimaNodoHoja();
	this->capacidadMaximaNodosHoja = config->getCapacidadMaximaNodoHoja();
	this->ultimoElementoLeido = NULL;

	switch (this->archivoNodos->getCantidadDeEstructuras()) {
	case (0):
		this->raiz = new NodoHoja(0, capacidadMinimaNodosHoja, capacidadMaximaNodosHoja);
		this->raiz->setNivel(0);
		this->raiz->setNumeroNodo(0);
		this->archivoNodos->insertar(this->raiz);
		break;
	case (1):
		this->raiz = new NodoHoja(0, capacidadMinimaNodosHoja, capacidadMaximaNodosHoja);
		this->raiz->setNivel(0);
		this->raiz->setNumeroNodo(0);
		this->archivoNodos->leer(this->raiz,0);
		break;
	default:
		this->raiz = new NodoInterno(capacidadMinimaNodosInternos, capacidadMaximaNodosInternos);
		this->archivoNodos->leer(this->raiz, 0);
	}
}

void ArbolBMas::insertar(string clave, unsigned int dato) {

	RegistroArbol* registroAInsertar = new RegistroArbol(clave);
	registroAInsertar->getOffsets()->push_back(dato);

	int cantidadDeRegistros = this->raiz->getRegistros()->size();

	Utils::ResultadoOperacionArbol resultado = this->insertarInterno(this->raiz, registroAInsertar);

	switch (resultado) {

	case Utils::SOBREFLUJO: {

		if (this->raiz->getNivel() != 0) {

			// creo dos nodos internos nuevos
			NodoInterno* hijoIzquierdo = new NodoInterno(this->capacidadMinimaNodosInternos,
					this->capacidadMaximaNodosInternos);
			NodoInterno* hijoDerecho = new NodoInterno(this->capacidadMinimaNodosInternos,
					this->capacidadMaximaNodosInternos);

			//balanceo la carga de la raiz entre ellos y les seteo el nivel
			this->balancearRaiz(raiz, hijoIzquierdo, hijoDerecho);
			hijoIzquierdo->setNivel(this->raiz->getNivel());
			hijoDerecho->setNivel(this->raiz->getNivel());

			//borro primer registro del nodo hijo derecho de la raiz para que no figure en su hijo derecho.
			string claveRaiz = hijoDerecho->getRegistros()->at(0)->getClave();
			delete hijoDerecho->getRegistros()->at(0);
			hijoDerecho->getRegistros()->erase(hijoDerecho->getRegistros()->begin());

			//los guardo
			unsigned int numeroDeNodoHijoDerecho = this->crearNodoNuevo(hijoDerecho);
			unsigned int numeroDeNodoHijoIzquierdo = this->crearNodoNuevo(hijoIzquierdo);

			//actualizo la raiz y la convierto en Nodo Interno
			Nodo* nuevaRaiz = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
			nuevaRaiz->setNivel(this->raiz->getNivel() + 1);
			nuevaRaiz->setNumeroNodo(this->raiz->getNumeroNodo());
			RegistroArbol* registroDeLaRaiz = new RegistroArbol(claveRaiz);
			registroDeLaRaiz->setReferenciaNodoIzquierdo(numeroDeNodoHijoIzquierdo);
			registroDeLaRaiz->setReferenciaNodoDerecho(numeroDeNodoHijoDerecho);
			nuevaRaiz->agregar(registroDeLaRaiz);
			delete this->raiz;
			delete hijoIzquierdo;
			delete hijoDerecho;

			this->raiz = nuevaRaiz;

		} else {
			// creo dos nodos hoja nuevos
			NodoHoja* hijoIzquierdo = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
			NodoHoja* hijoDerecho = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);

			//balanceo la carga de la raiz entre ellos y les seteo el nivel
			this->balancearRaiz(raiz, hijoIzquierdo, hijoDerecho);

			//los guardo (actualizo referencia a nodo siguiente del segundo antes)
			unsigned int numeroDeNodoHijoDerecho = this->crearNodoNuevo(hijoDerecho);
			hijoIzquierdo->setReferenciaNodoSiguiente(numeroDeNodoHijoDerecho);
			unsigned int numeroDeNodoHijoIzquierdo = this->crearNodoNuevo(hijoIzquierdo);

			//actualizo la raiz y la convierto en Nodo Interno
			Nodo* nuevaRaiz = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
			nuevaRaiz->setNivel(this->raiz->getNivel() + 1);
			nuevaRaiz->setNumeroNodo(this->raiz->getNumeroNodo());
			RegistroArbol* registroDeLaRaiz = new RegistroArbol(hijoDerecho->getRegistros()->at(0)->getClave());
			registroDeLaRaiz->setReferenciaNodoIzquierdo(numeroDeNodoHijoIzquierdo);
			registroDeLaRaiz->setReferenciaNodoDerecho(numeroDeNodoHijoDerecho);
			nuevaRaiz->agregar(registroDeLaRaiz);
			delete this->raiz;
			delete hijoIzquierdo;
			delete hijoDerecho;

			this->raiz = nuevaRaiz;
		}
		this->actualizarNodo(this->raiz);
		break;
	}
	case Utils::ACTUALIZADO:
		this->actualizarNodo(this->raiz);
		break;

	case Utils::OK:
	default:

		break;
	}
}

Utils::ResultadoOperacionArbol ArbolBMas::insertarInterno(Nodo* nodo, RegistroArbol* dato) {

	unsigned int nivelDelNodo = nodo->getNivel();

	if (nivelDelNodo == 0) {
		return nodo->agregar(dato);

	} else {

		// instancio al hijo y le seteo el nivel
		Nodo* nodoHijo;
		if (nivelDelNodo - 1 == 0)
			nodoHijo = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
		else
			nodoHijo = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);

		nodoHijo->setNivel(nivelDelNodo - 1);
		unsigned int numeroNodo = ((NodoInterno*) nodo)->getNumeroNodoHijoALeer(dato->getClave());
		nodoHijo->setNumeroNodo(numeroNodo);
		this->getNodo(nodoHijo);

		// inserto el dato en el hijo
		Utils::ResultadoOperacionArbol resultado = this->insertarInterno(nodoHijo, dato);

		switch (resultado) {

		case Utils::SOBREFLUJO: {

			// creo al hermano y le seteo el nivel
			Nodo* nuevoHermano;
			if (nodoHijo->getNivel() == 0)
				nuevoHermano = new NodoHoja(((NodoHoja*) nodoHijo)->getReferenciaNodoSiguiente(),
						this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
			else
				nuevoHermano = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);

			nuevoHermano->setNivel(nivelDelNodo - 1);

			// balanceo la carga entre los hermanos
			this->balancearNodos(nodoHijo, nuevoHermano);

			// los guardo (actualizo referencia a nodo siguiente del izquierdo)
			unsigned int numeroDeNodoHijoDerecho = this->crearNodoNuevo(nuevoHermano);
			((NodoHoja*) nodoHijo)->setReferenciaNodoSiguiente(numeroDeNodoHijoDerecho);
			this->actualizarNodo(nodoHijo);

			//actualizo al padre con un nuevo registro
			RegistroArbol* registroInterno = new RegistroArbol(nuevoHermano->getRegistros()->at(0)->getClave());
			registroInterno->setReferenciaNodoIzquierdo(nodoHijo->getNumeroNodo());
			registroInterno->setReferenciaNodoDerecho(numeroDeNodoHijoDerecho);
			Utils::ResultadoOperacionArbol resultado = nodo->agregar(registroInterno);
			delete nuevoHermano;
			delete nodoHijo;
			return resultado;
		}

		case Utils::ACTUALIZADO: {
			this->actualizarNodo(nodoHijo);
			delete nodoHijo;
			return Utils::OK;
			break;
		}

		case Utils::OK:
		default:
			delete nodoHijo;
			return Utils::OK;
			break;
		}
	}

	return Utils::OK;
}

void ArbolBMas::suprimir(string clave, unsigned int dato) {

	RegistroArbol* registroARemover = new RegistroArbol(clave);
	registroARemover->getOffsets()->push_back(dato);

	Utils::ResultadoOperacionArbol resultado = this->suprimirInterno(this->raiz, registroARemover);

	switch (resultado) {

	case Utils::SUBFLUJO: {

		if (this->raiz->getNivel() > 0) {
			// creo una nueva raiz
			Nodo* nuevaRaiz;
			if (this->raiz->getNivel() - 1 == 0)
				nuevaRaiz = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
			else
				nuevaRaiz = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
			nuevaRaiz->setNivel(this->raiz->getNivel() - 1);
			nuevaRaiz->setNumeroNodo(this->raiz->getNumeroNodo());

			// recorro a los hijos de la raiz y cargo su información en la hoja
			for (unsigned int i = 0; i < this->raiz->getRegistros()->size(); i++) {

				if (i == 0) {
					this->llenarNodoCon(nuevaRaiz, this->raiz->getRegistros()->at(i)->getReferenciaNodoIzquierdo(),
							this->raiz->getNivel() - 1);
				}

				this->llenarNodoCon(nuevaRaiz, this->raiz->getRegistros()->at(i)->getReferenciaNodoDerecho(),
						this->raiz->getNivel() - 1);
			}

			// actualizo a la raizs
			delete this->raiz;
			this->raiz = nuevaRaiz;
			this->actualizarNodo(this->raiz);
			break;
		} else {
			//solo actualizo la raiz (que queda vacia)
			this->actualizarNodo(this->raiz);
			break;
		}
	}

	case Utils::ACTUALIZADO:
		this->actualizarNodo(this->raiz);
		break;

	case Utils::OK:
	default:
		break;
	}
}

Utils::ResultadoOperacionArbol ArbolBMas::suprimirInterno(Nodo* nodo, RegistroArbol* registro) {

	unsigned int nivelDelNodo = nodo->getNivel();

	if (nivelDelNodo == 0) {
		return nodo->remover(registro);

	} else {

		// instancio al hijo y le seteo el nivel
		Nodo* nodoHijo;
		if (nivelDelNodo - 1 == 0)
			nodoHijo = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
		else
			nodoHijo = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);

		nodoHijo->setNivel(nivelDelNodo - 1);
		unsigned int numeroNodo = ((NodoInterno*) nodo)->getNumeroNodoHijoALeer(registro->getClave());
		nodoHijo->setNumeroNodo(numeroNodo);
		this->getNodo(nodoHijo);

		// remuevo el dato en el hijo
		Utils::ResultadoOperacionArbol resultado = this->suprimirInterno(nodoHijo, registro);

		switch (resultado) {

		case Utils::SUBFLUJO: {

			Nodo* nodoHermanoIzquierdo = NULL;
			Nodo* nodoHermanoDerecho = NULL;
			Utils::ResultadoOperacionArbol resultadoSubflujo = Utils::OK;

			bool pudeResolver = false;

			// voy a buscar al hermano derecho por default
			unsigned int numeroNodoHnoDerecho = ((NodoInterno*) nodo)->getHermanoDerechoDe(nodoHijo->getNumeroNodo());

			// si tiene intento balancear
			if (numeroNodoHnoDerecho != 0) {

				if (nivelDelNodo - 1 == 0)
					nodoHermanoDerecho
							= new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
				else
					nodoHermanoDerecho = new NodoInterno(this->capacidadMinimaNodosInternos,
							this->capacidadMaximaNodosInternos);

				nodoHermanoDerecho->setNivel(nivelDelNodo - 1);
				nodoHermanoDerecho->setNumeroNodo(numeroNodoHnoDerecho);
				this->getNodo(nodoHermanoDerecho);

				if (nodoHermanoDerecho->getRegistros()->size() > 1) {
					this->balancearNodos(nodoHermanoDerecho, nodoHijo);
					pudeResolver = true;
					this->actualizarNodo(nodoHermanoDerecho);

					//actualizo la clave del padre padre
					((NodoInterno*) nodo)->actualizarClaveDe(nodoHermanoDerecho->getNumeroNodo(),
							nodoHermanoDerecho->getRegistros()->at(0)->getClave());
				}
				this->actualizarNodo(nodoHijo);
				delete nodoHermanoDerecho;
				resultadoSubflujo = Utils::ACTUALIZADO;
			}

			// si no tiene o no puede balancear busco al izquierdo
			if (!pudeResolver) {

				unsigned int numeroNodoHnoIzquierdo = ((NodoInterno*) nodo)->getHermanoIzquierdoDe(
						nodoHijo->getNumeroNodo());

				// si tiene intento balancear
				if (numeroNodoHnoIzquierdo != 0) {

					if (nivelDelNodo - 1 == 0)
						nodoHermanoIzquierdo = new NodoHoja(0, this->capacidadMinimaNodosHoja,
								this->capacidadMaximaNodosHoja);
					else
						nodoHermanoIzquierdo = new NodoInterno(this->capacidadMinimaNodosInternos,
								this->capacidadMaximaNodosInternos);

					nodoHermanoIzquierdo->setNivel(nivelDelNodo - 1);
					nodoHermanoIzquierdo->setNumeroNodo(numeroNodoHnoIzquierdo);
					this->getNodo(nodoHermanoIzquierdo);

					if (nodoHermanoIzquierdo->getRegistros()->size() > 1) {
						this->balancearNodos(nodoHermanoIzquierdo, nodoHijo);
						pudeResolver = true;
						this->actualizarNodo(nodoHermanoIzquierdo);

						//actualizo la clave del padre padre
						((NodoInterno*) nodo)->actualizarClaveDe(nodoHijo->getNumeroNodo(),
								nodoHijo->getRegistros()->at(0)->getClave());
					}
					this->actualizarNodo(nodoHijo);
					delete nodoHermanoIzquierdo;
					resultadoSubflujo = Utils::ACTUALIZADO;
				}
			}

			// si no pude balancear nunca, remuevo al nodoHijo del padre y marco al hijo como borrado
			if (!pudeResolver) {
				RegistroArbol* temp = new RegistroArbol("temp");
				temp->setReferenciaNodoIzquierdo(nodoHijo->getNumeroNodo());
				nodo->remover(temp);
				this->nodosLibres->insertarEstructuraLibre(nodoHijo->getNumeroNodo());
				delete temp;
				resultadoSubflujo = Utils::ACTUALIZADO;
			}

			// NOTESE que no se actualiza un nodo que no resuelve su subflujo
			delete nodoHijo;
			return resultadoSubflujo;
		}

		case Utils::ACTUALIZADO: {
			this->actualizarNodo(nodoHijo);
			delete nodoHijo;
			return Utils::OK;
			break;
		}

		case Utils::OK:
		default:
			delete nodoHijo;
			return Utils::OK;
			break;
		}
	}

	return Utils::OK;
}

/* Balancea la carga entre los dos nodos (50% para cada uno, con un tope de carga máxima) */
Utils::ResultadoOperacionArbol ArbolBMas::balancearNodos(Nodo* hermanoIzquierdo, Nodo* hermanoDerecho) {

	//obtengo el 50% de la carga total
	unsigned int cargaMinimaDelIzquierdo = (hermanoIzquierdo->getTamanioDelBuffer()
			+ hermanoDerecho->getTamanioDelBuffer()) / 2;

	// cargo todos los registros en un vector temporal y limpio a los nodos
	vector<RegistroArbol*>* temp = new vector<RegistroArbol*> ();
	temp->insert(temp->begin(), hermanoIzquierdo->getRegistros()->begin(), hermanoIzquierdo->getRegistros()->end());
	temp->insert(temp->end(), hermanoDerecho->getRegistros()->begin(), hermanoDerecho->getRegistros()->end());
	hermanoIzquierdo->getRegistros()->clear();
	hermanoDerecho->getRegistros()->clear();

	for (unsigned int i = 0; i < temp->size(); i++) {

		bool supereLaCargaMinima = hermanoIzquierdo->getTamanioDelBuffer() >= cargaMinimaDelIzquierdo;
		bool supereLaCargaMaxima = hermanoIzquierdo->getTamanioDelBuffer() >= hermanoIzquierdo->getCapacidadMaxima();

		if (!supereLaCargaMinima && !supereLaCargaMaxima)
			hermanoIzquierdo->agregar(temp->at(i));
		else {
			hermanoDerecho->agregar(temp->at(i));
		}
	}

	delete temp;
	return Utils::ACTUALIZADO;
}

/* Balanceamos los registros de la raiz entre sus dos hijos. Para ello intentamos llenar el hijo izquierdo con un valor
 * entre el 50% y el 100% de su capacidad máxima y al derecho con el resto (hay casos donde esto puede no suceder) */
Utils::ResultadoOperacionArbol ArbolBMas::balancearRaiz(Nodo* raiz, Nodo* hijoIzquierdo, Nodo* hijoDerecho) {

	//obtengo el 50% de la carga total
	unsigned int cargaMinimaDelIzquierdo = (raiz->getTamanioDelBuffer()) / 2;

	// cargo todos los registros en un vector temporal y limpio a la raiz
	vector<RegistroArbol*>* temp = new vector<RegistroArbol*> ();
	temp->insert(temp->begin(), raiz->getRegistros()->begin(), raiz->getRegistros()->end());
	raiz->getRegistros()->clear();

	for (unsigned int i = 0; i < temp->size(); i++) {

		bool supereLaCargaMinima = hijoIzquierdo->getTamanioDelBuffer() >= cargaMinimaDelIzquierdo;
		bool supereLaCargaMaxima = hijoIzquierdo->getTamanioDelBuffer() >= hijoIzquierdo->getCapacidadMaxima();

		if (!supereLaCargaMinima && !supereLaCargaMaxima)
			hijoIzquierdo->getRegistros()->push_back(temp->at(i));
		else
			hijoDerecho->getRegistros()->push_back(temp->at(i));
	}

	delete temp;
	return Utils::ACTUALIZADO;
}

void ArbolBMas::llenarNodoCon(Nodo* nodoALlenar, unsigned int numeroDeNodoAVaciar, unsigned int nivelDeNodoAVaciar) {

	Nodo* nodoAVaciar;

	if (nivelDeNodoAVaciar == 0)
		nodoAVaciar = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
	else
		nodoAVaciar = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);

	nodoAVaciar->setNivel(nivelDeNodoAVaciar);
	this->getNodo(nodoAVaciar);

	for (unsigned int i = 0; i < nodoAVaciar->getRegistros()->size(); i++) {

		nodoALlenar->agregar(nodoAVaciar->getRegistros()->at(i));
	}
	this->nodosLibres->insertarEstructuraLibre(nodoAVaciar->getNumeroNodo());
	delete nodoAVaciar;
}

void ArbolBMas::actualizarNodo(Nodo* nodo) {

	this->archivoNodos->modificar(nodo, nodo->getNumeroNodo());
}

void ArbolBMas::getNodo(Nodo *nodo) {
	this->archivoNodos->leer(nodo, nodo->getNumeroNodo());
}

/*Inserta el nodo pasado por parámetro en el archivo y devuelve la posición donde se insertó (número de nodo) */
unsigned int ArbolBMas::crearNodoNuevo(Nodo* nodoACrear) {

	int numeroDelNodoNuevo = -1;
	int nodoLibre = this->nodosLibres->obtenerEstructuraLibre();

	if (nodoLibre != -1) {
		nodoACrear->setNumeroNodo(nodoLibre);
		numeroDelNodoNuevo = this->archivoNodos->modificar(nodoACrear, nodoACrear->getNumeroNodo());
	} else {
		numeroDelNodoNuevo = this->archivoNodos->insertar(nodoACrear);
	}

	return numeroDelNodoNuevo;
}

void ArbolBMas::exportar() {

	/*Compruebo si el archivo de texto existe, de ser asi lo elimino para crear uno nuevo*/
	ofstream archivoArbolTexto("ArbolBMas.txt");
	if (archivoArbolTexto.is_open())
		remove("ArbolBMas.txt");

	/*Recorro el arbol en preorder para imprimirlo a un archivo txt.*/
	preOrder(this->raiz);
}

void ArbolBMas::preOrder(Nodo* nodo) {

	/*Escribimos el nodo en el archivo de texto.*/
	escribirEnARchivo(nodo);

	/*Evaluo para saber que tipo de nodo debo instanciar.*/
	switch (nodo->getNivel() - 1) {

	case (0): {

		/*Recorro todos los registros del nodo para instanciar cada referencia izquierda como nodo hoja y escribirlos en el archivo.*/
		for (unsigned int i = 0; i < nodo->getRegistros()->size(); i++) {
			NodoHoja * nodoHoja = new NodoHoja(nodo->getRegistros()->at(i)->getReferenciaNodoDerecho(),
					this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
			nodoHoja->setNumeroNodo(nodo->getRegistros()->at(i)->getReferenciaNodoIzquierdo());
			this->getNodo(nodoHoja);
			preOrder(nodoHoja);
			delete nodoHoja;
		}

		/*Pongo referencia nodo siguiente = 99 (en cualquier valor) porque ya la obtengo al leer el nodo.
		 *Instancio como nodo interno la ultima referencia del nodo.*/
		NodoHoja* nodoHoja = new NodoHoja(99, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
		nodoHoja->setNumeroNodo(nodo->getRegistros()->at(nodo->getRegistros()->size() - 1)->getReferenciaNodoDerecho());
		this->getNodo(nodoHoja);
		preOrder(nodoHoja);
		delete nodoHoja;
		break;
	}

	case (-1):
		/*Valor de corte de control.*/
		break;

	default: {

		/*Recorro todos los registros del nodo para instanciar cada referencia izquierda como nodo interno y escribirlos en el archivo.*/
		for (unsigned int i = 0; i < nodo->getRegistros()->size(); i++) {
			NodoInterno* nodoInterno = new NodoInterno(this->capacidadMinimaNodosInternos,
					this->capacidadMaximaNodosInternos);
			nodoInterno->setNumeroNodo(nodo->getRegistros()->at(i)->getReferenciaNodoIzquierdo());
			this->getNodo(nodoInterno);
			preOrder(nodoInterno);
			delete nodoInterno;
		}

		/*Instancio como nodo interno la ultima referencia del nodo.*/
		NodoInterno* nodoInterno = new NodoInterno(this->capacidadMinimaNodosInternos,
				this->capacidadMaximaNodosInternos);
		nodoInterno->setNumeroNodo(
				nodo->getRegistros()->at(nodo->getRegistros()->size() - 1)->getReferenciaNodoDerecho());
		this->getNodo(nodoInterno);
		preOrder(nodoInterno);
		delete nodoInterno;
		break;
	}
	}
}

void ArbolBMas::escribirEnARchivo(Nodo* nodo) {

	/*Abro archivo y me posiciono al final para escribir.*/
	ofstream archivoArbolTexto;
	archivoArbolTexto.open("ArbolBMas.txt", ios::app);

	if (nodo->getNivel() == 0) {

		/*Imprimo formato del nodo hoja.*/
		archivoArbolTexto << "NODO " << nodo->getNumeroNodo() << "  (" << nodo->getRegistros()->size()
				<< " elemento/s )" << endl;
		for (unsigned int i = 0; i < nodo->getRegistros()->size(); i++) {
			archivoArbolTexto << "( " + nodo->getRegistros()->at(i)->getClave() + ") ";
		}
		archivoArbolTexto << "\nSiguiente hoja: " << ((NodoHoja*) nodo)->getReferenciaNodoSiguiente() << "\n" << endl;

	} else {

		/*Imprimo formato del nodo interno.*/
		archivoArbolTexto << "NODO " << nodo->getNumeroNodo() << "  (" << nodo->getRegistros()->size()
				<< " elemento/s )" << endl;
		for (unsigned int i = 0; i < nodo->getRegistros()->size(); i++) {
			archivoArbolTexto << nodo->getRegistros()->at(i)->getReferenciaNodoIzquierdo();
			archivoArbolTexto << "( " + nodo->getRegistros()->at(i)->getClave() + ") ";
		}
		archivoArbolTexto << nodo->getRegistros()->at(nodo->getRegistros()->size() - 1)->getReferenciaNodoDerecho()
				<< "\n" << endl;
	}

	/*Cierro el archivo.*/
	archivoArbolTexto.close();
}

/*Modifica el offset de una clave con un offset nuevo.*/
void ArbolBMas::modificar(string clave, unsigned int datoViejo, unsigned int datoNuevo) {

	unsigned int numeroNodoHoja = this->getNumeroNodoHojaPorClave(this->raiz, clave);

	Nodo* nodoHoja = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
	nodoHoja->setNumeroNodo(numeroNodoHoja);
	this->getNodo(nodoHoja);

	for (unsigned int i = 0; i < nodoHoja->getRegistros()->size(); ++i) {
		if (nodoHoja->getRegistros()->at(i)->getClave() == clave) {
			for (unsigned int j = 0; j < nodoHoja->getRegistros()->at(i)->getOffsets()->size(); j++) {
				if (nodoHoja->getRegistros()->at(i)->getOffsets()->at(j) == datoViejo) {
					nodoHoja->getRegistros()->at(i)->getOffsets()->at(j) = datoNuevo;
					actualizarNodo(nodoHoja);
					break;
				}
			}
			break;
		}
	}
	delete nodoHoja;
}

/*Recorre el árbol hasta llegar a la hoja que contiene la clave y devuelve el número de nodo de la hoja.*/
unsigned int ArbolBMas::getNumeroNodoHojaPorClave(Nodo* nodo, string clave) {

	switch (nodo->getNivel() - 1) {

	// La clave está (o tendría que estar) en el nodo que es pasado por parámetro, que es hoja
	case (-1): {
		return nodo->getNumeroNodo();
	}
		//El siguiente es hoja
	case (0): {
		int nodoALeer = ((NodoInterno*) nodo)->getNumeroNodoHijoALeer(clave);
		Nodo* nodoHijo = new NodoHoja(0, this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
		nodoHijo->setNumeroNodo(nodoALeer);
		this->getNodo(nodoHijo);
		unsigned int numeroNodo = this->getNumeroNodoHojaPorClave(nodoHijo, clave);
		delete nodoHijo;
		return numeroNodo;
	}
		//El siguiente es interno
	default: {
		int nodoALeer = ((NodoInterno*) nodo)->getNumeroNodoHijoALeer(clave);
		Nodo* nodoHijo = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
		nodoHijo->setNumeroNodo(nodoALeer);
		this->getNodo(nodoHijo);
		unsigned int numeroNodo = this->getNumeroNodoHojaPorClave(nodoHijo, clave);
		delete nodoHijo;
		return numeroNodo;
	}
	}
}

RegistroArbol* ArbolBMas::siguiente() {

	if (this->raiz->getRegistros()->size() > 0) {

		if (this->ultimoElementoLeido == NULL) {
			this->ultimoElementoLeido = getRegistroMasChicoEnArbol(this->raiz);
			return this->ultimoElementoLeido;
		} else {
			unsigned int numeroNodoHoja = this->getNumeroNodoHojaPorClave(this->raiz,
					this->ultimoElementoLeido->getClave());

			NodoHoja* nodoHoja =
					new NodoHoja(0, this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
			nodoHoja->setNumeroNodo(numeroNodoHoja);
			this->getNodo(nodoHoja);

			unsigned int posicionRegistro;
			for (posicionRegistro = 0; posicionRegistro < nodoHoja->getRegistros()->size(); posicionRegistro++) {
				if (nodoHoja->getRegistros()->at(posicionRegistro)->getClave() == this->ultimoElementoLeido->getClave())
					break;
			}

			// si el siguiente es mayor que el size -1, es porque está en otra hoja. Pero si es la raiz, no hay siguiente
			if ((posicionRegistro + 1 > nodoHoja->getRegistros()->size() - 1)
					&& (nodoHoja->getReferenciaNodoSiguiente() == this->raiz->getNumeroNodo()))
				return this->ultimoElementoLeido;
			else {

				if (posicionRegistro + 1 > nodoHoja->getRegistros()->size() - 1) {

					NodoHoja* nodoHojaSiguiente = new NodoHoja(0, this->capacidadMinimaNodosInternos,
							this->capacidadMaximaNodosInternos);
					nodoHojaSiguiente->setNumeroNodo(nodoHoja->getReferenciaNodoSiguiente());
					this->getNodo(nodoHojaSiguiente);
					this->ultimoElementoLeido = nodoHojaSiguiente->getRegistros()->at(0);
					//					delete nodoHojaSiguiente;
					return this->ultimoElementoLeido;

				} else {
					this->ultimoElementoLeido = nodoHoja->getRegistros()->at(posicionRegistro + 1);
					return this->ultimoElementoLeido;
				}
			}
			//			delete nodoHoja;
		}
	} else {
		this->ultimoElementoLeido = NULL;
		return this->ultimoElementoLeido;
	}
}

RegistroArbol* ArbolBMas::getRegistroMasChicoEnArbol(Nodo* nodo) {

	RegistroArbol* registroADevolver = NULL;

	if (nodo->getNivel() == 0) {
		RegistroArbol* registroMasChico = nodo->getRegistros()->at(0);

		registroADevolver = new RegistroArbol(registroMasChico->getClave());
		registroADevolver->getOffsets()->insert(registroADevolver->getOffsets()->begin(),
				registroMasChico->getOffsets()->begin(), registroMasChico->getOffsets()->end());
		registroADevolver->setReferenciaNodoIzquierdo(registroMasChico->getReferenciaNodoIzquierdo());
		registroADevolver->setReferenciaNodoDerecho(registroMasChico->getReferenciaNodoDerecho());

		return registroADevolver;
	} else {
		Nodo* nodoSiguiente;
		if (nodo->getNivel() - 1 > 0)
			nodoSiguiente = new NodoInterno(this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
		else
			nodoSiguiente = new NodoHoja(0, this->capacidadMinimaNodosHoja, this->capacidadMaximaNodosHoja);
		nodoSiguiente->setNumeroNodo(nodo->getRegistros()->at(0)->getReferenciaNodoIzquierdo());
		this->getNodo(nodoSiguiente);
		registroADevolver = getRegistroMasChicoEnArbol(nodoSiguiente);

		delete nodoSiguiente;
	}

	return registroADevolver;
}

IRegistroIndice* ArbolBMas::buscar(string clave) {

	RegistroArbol* registroADevolver = NULL;
	bool encontreLaClave = false;

	// devuelve el numero de hoja donde tendrìa que estar la clave buscada
	int numeroNodoHoja = this->getNumeroNodoHojaPorClave(this->raiz, clave);

	NodoHoja* nodoHoja = new NodoHoja(0, this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
	nodoHoja->setNumeroNodo(numeroNodoHoja);
	this->getNodo(nodoHoja);

	unsigned int posicionRegistro;
	for (posicionRegistro = 0; posicionRegistro < nodoHoja->getRegistros()->size(); posicionRegistro++) {
		if (nodoHoja->getRegistros()->at(posicionRegistro)->getClave() == clave) {
			encontreLaClave = true;
			break;
		}
	}

	if (!encontreLaClave) {

		bool esMenor = false;
		for (posicionRegistro = 0; posicionRegistro < nodoHoja->getRegistros()->size(); posicionRegistro++) {
			if (nodoHoja->getRegistros()->at(posicionRegistro)->getClave() > clave) {
				esMenor = true;
				break;
			}
		}

		//es mas grande que todas las claves del nodo.
		if (!esMenor) {

			// està en el siguiente nodo
			unsigned int numeroHermanoSiguiente = nodoHoja->getReferenciaNodoSiguiente();
			delete nodoHoja;

			// si el siguiente es la raiz devuelvo nulo
			if (numeroHermanoSiguiente != 0) {
				nodoHoja = new NodoHoja(0, this->capacidadMinimaNodosInternos, this->capacidadMaximaNodosInternos);
				nodoHoja->setNumeroNodo(numeroHermanoSiguiente);
				this->getNodo(nodoHoja);
				posicionRegistro = 0;
			} else
				return NULL;
		}
	}

	RegistroArbol* registroEncontrado = nodoHoja->getRegistros()->at(posicionRegistro);

	registroADevolver = new RegistroArbol(registroEncontrado->getClave());
	registroADevolver->getOffsets()->insert(registroADevolver->getOffsets()->begin(),
			registroEncontrado->getOffsets()->begin(), registroEncontrado->getOffsets()->end());
	registroADevolver->setReferenciaNodoIzquierdo(registroEncontrado->getReferenciaNodoIzquierdo());
	registroADevolver->setReferenciaNodoDerecho(registroEncontrado->getReferenciaNodoDerecho());
	delete nodoHoja;
	return registroADevolver;
}

ArbolBMas::~ArbolBMas() {
	delete archivoNodos;
	delete nodosLibres;
	delete raiz;

	if (this->ultimoElementoLeido != NULL)
		delete this->ultimoElementoLeido;
}

